from LineValues.D import D 
from LineValues.DNot import DNot
from LineValues.One import One
from LineValues.X import X
from LineValues.Zero import Zero
from Gates.Gate import Gate
from Gates.ANDGate import AndGate 
from Gates.NANDGate import NandGate 
from Gates.NORGate import NorGate 
from Gates.NOTGate import NotGate 
from Gates.ORGate import OrGate 
from Gates.XNORGate import XnorGate 
from Gates.XORGate import XorGate 
from Simulator import simulate
from Wire import Wire

from parse import parse #for testing purposes 

"""
faultWire should be the actual wire object, not just the name of the wire
faultValue: pass in 1 or 0, corresponding to stuck at 1 or stuck at 0
"""
def podem(faultWire, stuckValue, pInputs, pOutputs, wires, gates):
	print "++++++++++++++++++++++++++++++++"
	faultWire.printSelf
	printVal(stuckValue)
	print "+++++++++++++++++++++++++++++++++"

	nextWire = faultWire
	nextVal = ""
	faultValue = None

	if stuckValue is One: 
		nextVal = DNot
		faultValue = DNot
	else: 
		nextVal = D
		faultValue = D 

	faultWire.setStuckAt(stuckValue)

	pIPath = [] #Most recent PI set in slot 0 
	switchedPIs = []
	inputVector = []
	originPISwitched = False
	for count in range(len(pInputs)):
		inputVector.append(X)

	simulate(inputVector, pInputs, pOutputs, wires, gates)
	print "++++++++++++++++++++++++++++++++++++++++++++++++"
	print "Fault Info:"
	faultWire.printSelf()
	printVal(faultValue)
	print "++++++++++++++++++++++++++++++++++++++++++++++++"

	while True:

		print "Objective Info: "
		nextWire.printSelf()
		printVal(nextVal)
		print "++++++++++++++++++++++++++++++++++++++++++++++++"

		pInput, pValue = backTrace(nextWire, nextVal, pIPath, faultWire)
		print "Backtrace Info: "
		pInput.printSelf()
		printVal(pValue)
		print "++++++++++++++++++++++++++++++++++++++++++++++++"

		inputVector[pInputs.index(pInput)] = pValue 
		print "Input Vector: "
		print getPrintableInputVecs(inputVector)
		print "++++++++++++++++++++++++++++++++++++++++++++++++"

		result = simulate(inputVector, pInputs, pOutputs, wires, gates)

		if checkPOuts(pOutputs) == True:
			print "checkPOuts success"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			break

		xPathData = xPathCheck(faultWire, faultValue, pOutputs)
		
		if xPathData[0] == False:
			print "xPathCheck Failed, backTrack time"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			btInfo = backTrack(pIPath, inputVector, switchedPIs, pInputs, pOutputs, wires, gates, originPISwitched, faultWire, faultValue)

			if btInfo[0] == True: 
				"backTrack successful"
				print "++++++++++++++++++++++++++++++++++++++++++++++++"
				nextWire = btInfo[1]
				nextVal = btInfo[2]
			elif btInfo[0] == False: 
				print "BackTrack failed, fault untestable"
				print "++++++++++++++++++++++++++++++++++++++++++++++++"
				inputVector.append("BLEH")
				break
		else: 
			nextWire = xPathData[1]
			nextVal = xPathData[2]
			print "xPathCheck Succeeded"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"

		if checkPOuts(pOutputs) == True:
			print "checkPOuts success"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			break
			

	faultWire.isStuck = False
	faultWire.stuckValue = None 
	return (faultWire, stuckValue, inputVector)

"""
ALWAYS called on the faulty wire. 
Is deterministic. Ie, this won't work right on any python version without stable sort  
getObjective works through fanouts, thus a wire that fans out will never be returned. 

returns (True/False, wire/0, val/0)
"""
def getObjective(frontWire, value, faultWire):
	print "Entering getObjective"
	print "++++++++++++++++++++++++++++++++++++++++++++++++"

	if frontWire is faultWire and frontWire.value is X: 
		print "Objective is fault, and fault is X"
		frontWire.printSelf()
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		return (True, frontWire, value) 

	elif len(frontWire.destinations) == 0 and (frontWire.value is X or frontWire.value is D or frontWire.value is DNot):
		print "Objective frontwire is a pO and equal to X, D, or Dnot"
		frontWire.printSelf()
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		return (True, frontWire, value)
	
	elif len(frontWire.destinations) == 1: #implies that the destination is a gate

		print "Objective frontWire leads to a gate"
		nextVal = value
		gate = frontWire.destinations[0]
		print "Objetive frontgate:"
		gate.printSelf()

		if gate.output.value is Zero or gate.output.value is One:
			print "GateOutput already set to Zero or One" 
			return (False, 0, 0)

		if type(gate) is NandGate or type(gate) is NorGate or type(gate) is NotGate: 
			nextVal = value.NOT()

		print "Objective gate output"
		gate.output.printSelf()
		print "Objective gate output desired value"
		printVal(nextVal)
		print "++++++++++++++++++++++++++++++++++++++++++++++++"

		if gate.output.value is X: 
			print "Objective gate output is X, it's the new frontier"
			return (True, gate.output, nextVal)

		objData = getObjective(gate.output, nextVal, faultWire)
		if objData[0] is True: 
			return objData

	else: #Fantout. XPath is responsible for redirecting getObjective if need be, so no loop from not marking exhausted
		print "Objective fans out"
		sDestinations = sorted(frontWire.destinations, key=lambda wire: wire.observability)
		for dest in sDestinations: 
			objData = getObjective(dest, value, faultWire)
			if objData[0] is True: 
				print "Objective fanout branch found"
				dest.printSelf()
				print "++++++++++++++++++++++++++++++++++++++++++++++++"
				if dest.value is X:
					return (True, dest, value)
				else:
					return objData

	return (False, 0, 0)


"""
wire and value should be whatever getObjective returns. 
When backtracing from a D/DNot, we obviously want to backtrace to a noncontrolling value
"""
def backTrace(wire, value, pIPath, faultWire):
	desiredVal = value  

	if wire.source == None:
		pIPath.insert(0, wire)
		if desiredVal is D:
			desiredVal = One  
		elif desiredVal is DNot: 
			desiredVal = Zero
		return wire, desiredVal

	if isinstance(wire.source, Gate) == True:
		gate = wire.source

		if faultWire.value is X: 
			if desiredVal is D: 
				desiredVal = One
			elif desiredVal is DNot: 
				desiredVal = Zero

		checkInputReqs = allInputsRequired(wire.source, desiredVal)
		nextWire = ""

		print "Backtrace Gate"
		gate.printSelf()

		if checkInputReqs == False:
			print "select easiest input"
			nextWire = getNextEasiestInput(gate) #we want a controlling value from the input
		elif checkInputReqs == True:
			print "select hardest input"
			nextWire = getNextHardestInput(gate) #we want a noncontrolling value from the input 
		
		if type(gate) is NotGate or type(gate) is NandGate or type(gate) is NorGate:
			if desiredVal is Zero:
				desiredVal = One
			elif desiredVal is One:
				desiredVal = Zero

		if desiredVal is D or desiredVal is DNot: 
			if type(gate) is XorGate or type(gate) is XnorGate:
				if nextWire.zeroControllability < nextWire.oneControllability:
					desiredVal = Zero
				else: 
					desiredVal = One
			else:    
				desiredVal = getNonControllingInput(wire.source)

		print "Backtrace gate input line"
		nextWire.printSelf()
		print "Backtrace gate input value"
		printVal(desiredVal)
			
		return backTrace(nextWire, desiredVal, pIPath, faultWire)

	elif type(wire.source) is Wire:
		return backTrace(wire.source, desiredVal, pIPath, faultWire)

"""

"""
def backTrack(pIPath, inputVector, switchedPIs, pInputs, pOutputs, wires, gates, originPISwitched, faultWire, faultValue):

	success = (False, 0) 
	print "Entering Backtrack"
	print "++++++++++++++++++++++++++++++++++++++++++++++++"
	btAgain = False
	

	if len(pIPath) == 1: #The origin PI! If we have already switched it, the fault is untestable
		print "Backtracking origin"
		print "++++++++++++++++++++++++++++++++++++++++++++++++" 
		if originPISwitched == True:
			print "Origin was already switched fault untestable"
			print "++++++++++++++++++++++++++++++++++++++++++++++++" 
			return (False, 0) 
		else: 
			print "switching origin"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			originPISwitched = True 

	if len(pIPath) == 0: 
		print "Nothing to backtrack, we are fucked"
		return (False, 0)

	pi = pIPath[0]
	
	"""
	IF: Takes are of situation where we encoutered a previously switched primary input 
	If we previously switched this input, we set this primary input to X on the inputVec 
	and take it out of both the switchedPIs and pIPath. We only check for a valid xPath 
	on first switchs to make sure we don't repeat ourselves  
	
	ELSE: Switching pIs for the first time occurs here. If xPathCheck returns false, we call backTrack 
	again, essentially moving backwards up the pI tree since it's guarunteed that on the next call 
	the first pI seen will be switchedPIs[0]
	"""

	print "PI we are working with:"
	pi.printSelf()
	print "++++++++++++++++++++++++++++++++++++++++++++++++"
	if len(switchedPIs) > 0 and switchedPIs[0] is pi:
		print "PI already switched!"
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		inputVector[pInputs.index(pi)] = X
		pIPath.pop(0)
		switchedPIs.pop(0)
		btAgain = True

	else: 
		print "PI not switched"
		print "Current PI value: "
		printVal(pi.value)
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		index = pInputs.index(pi)
		print "PIIndex: " + str(index)
		print "Current inputVec val"
		printVal(inputVector[index])
		inputVector[index] = inputVector[index].NOT()
		print "New inputVec val"
		printVal(inputVector[index])
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		switchedPIs.insert(0, pIPath.pop(0))
		result = simulate(inputVector, pInputs, pOutputs, wires, gates)
		pathData = xPathCheck(faultWire, faultValue, pOutputs) 
		if pathData[0] == True:
			print "Backtrack worked!"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			success = pathData
		else: 
			print "Backtrack failed"
			print "++++++++++++++++++++++++++++++++++++++++++++++++"
			btAgain = True 

	if btAgain is True: 
		print "Backtrack party"
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		success = backTrack(pIPath, inputVector, switchedPIs, pInputs, pOutputs, wires, gates, originPISwitched, faultWire, faultValue)

	return success 

"""
I only care about violations of the faulty wire or 
if the d frontier disappears entirely. The problem with caring about values 
leading up to the faulty wire or specific objective paths is that a PI choice 
can ruin the path we are on but open up / keep open another one. 

If it returns true, then xPathCheck is responsible for 
redirecting the objective wire and value if need be

return format: (success/failure, [optional] wire, [optional] value) 

"""
def xPathCheck(faultWire, faultVal, pOuts):
	print "Entering xPathCheck"
	print "++++++++++++++++++++++++++++++++++++++++++++++++"

	#Checking faulty wire to make sure the fault is alive or possible
	if faultWire.value is One or faultWire.value is Zero: 
		print "xPathCheck: fault dead"
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		return (False, 0) #faultDead

	#Check to make sure at least one primary output is alive 
	outsAlive = False 
	for out in pOuts: 
		if out.value is X or out.value is D or out.value is DNot: 
			outsAlive = True
			break 
	if outsAlive == False: 
		print "xPathCheck: primary outputs all dead"
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		return (False, 0) 

	print "xPathCheck finding objective"
	print "++++++++++++++++++++++++++++++++++++++++++++++++"
	objInfo = getObjective(faultWire, faultVal, faultWire)

	if objInfo[0] is False: 
		print "xPathCheck objetive false!"
		print "++++++++++++++++++++++++++++++++++++++++++++++++"
		return (False, 0)
	else: 
		return objInfo

"""
Call this to figure out if a wire leads to a live po. It's kind of a could save time, could
waste it deal. Call this on wires in dFrontier
"""
def propagatesToAlivePOut(wire, pOuts):
	
	if len(wire.destinations) == 0 and (wire.value is X or wire.value is D or wire.value is DNot): 
		return True

	elif len(wire.destinations) == 1: #wire goes to gate
		gateOut = wire.destinations[0].output
		if gateOut.value is D or gateOut.value is DNot or gateOut.value is X: 
			return propagatesToAlivePOut(gateOut, pOuts)
	
	else: #wire fans out
		sDests = sorted(wire.destinations, key=lambda wire: wire.observability)
		for line in sDests: 
			pathAlive = propagatesToAlivePOut(line, pOuts)
			if pathAlive is True: 
				return True 

	return False 

def isControllingInput(gate, val): #Wire must go to gate, not fan out 
	if type(gate) is AndGate or type(gate) is NandGate: 
		if val is Zero: 
			return True 
	elif type(gate) is OrGate or type(gate) is NorGate:
		if val is One:
			return True
	elif type(gate) is XorGate or XnorGate: 
		return True

	return False 

def isControlledOutput(gate, val):
	if type(gate) is AndGate or type(gate) is NorGate: 
		if val is One: 
			return True 
	elif type(gate) is OrGate or type(gate) is NandGate: 
		if val is Zero: 
			return True 
	elif type(gate) is XorGate or type(gate) is XnorGate: 
		return True 

	return False 

def checkPOuts(pOutputs):
	val = False
	for out in pOutputs: 
		if out.value is D or out.value is DNot:
			val = True
			break 

	return val

def getNextHardestInput(gate):
	inputs = gate.inputs
	if type(gate) is AndGate or type(gate) is NandGate:
		sInputs = sorted(inputs, key=lambda wire: wire.oneControllability, reverse=True)
		for input in sInputs:
			if input.value is X:
				return input 
	elif type(gate) is NorGate or type(gate) is OrGate: 
		sInputs = sorted(inputs, key=lambda wire: wire.zeroControllability, reverse=True)
		for input in sInputs:
			if input.value is X:
				return input 
	elif type(gate) is NotGate:
		return inputs[0]
	elif type(gate) is XnorGate or type(gate) is XorGate:
		sInputs = sorted(inputs, key=lambda wire: abs(wire.zeroControllability - wire.oneControllability), reverse=True)
		oneCount = 0
		zeroCount = 0
		for input in inputs: 
			if input.value is X: 
				return input
	else: 
		print "hardest wtf?"

"""
Implie we want to set a controlling value, 
ie set a 0 into an And gate 
"""
def getNextEasiestInput(gate):
	inputs = gate.inputs 
	if type(gate) is AndGate or type(gate) is NandGate:
		sInputs = sorted(inputs, key=lambda wire: wire.oneControllability)
		for input in sInputs:
			if input.value is X:
				return input 
	elif type(gate) is NorGate or type(gate) is OrGate: 
		sInputs = sorted(inputs, key=lambda wire: wire.zeroControllability)
		for input in sInputs:
			if input.value is X:
				return input 
	elif type(gate) is NotGate:
		return inputs[0]
	elif type(gate) is XnorGate or type(gate) is XorGate:
		print "Why do you need the easiest input of a XorGate?"
	else: 
		print "easiest wtf?"

"""
For non Xor/Xnor gates, means that you want to set all the 
inputs to non controlling values. 
You always want to do this for DNot/D, which is why we 
only need to test one LineValue for each gate 
"""
def allInputsRequired(gate, value): 
	if type(gate) is AndGate:
		if value is Zero:
			return False
		else:
			return True
	elif type(gate) is NandGate: 
		if value is One:
			return False 
		else:
			return True 
	elif type(gate) is NorGate: 
		if value is Zero: 
			return False
		else:
			return True
	elif type(gate) is NotGate:
		return True 
	elif type(gate) is OrGate:
		if value is One:
			return False 
		else: 
			return True
	elif type(gate) is XnorGate:
		return True
	elif type(gate) is XorGate: 
		return True

def getPrintableInputVecs(inputVec):
	pList = []
	for val in inputVec: 
		if val is One: 
			pList.append("1")
		elif val is Zero: 
			pList.append("0")
		elif val is D: 
			pList.append("D")
		elif val is DNot: 
			pList.append("DNot")
		elif val is X: 
			pList.append("X")
		else: 
			print val
			pList.append("Wtf?")
	return pList

def printVal(val):
	if val is One: 
		print "One"
	elif val is Zero:
		print "Zero"
	elif val is D: 
		print "D"
	elif val is DNot:
		print "DNot"
	elif val is X: 
		print "X"
	else: 
		print "WtfVal?"

def getNonControllingInput(gate):
	if type(gate) is AndGate or type(gate) is NandGate: 
		return One 
	if type(gate) is OrGate or type(gate) is NorGate: 
		return Zero
	if type(gate) is XorGate or type(gate) is XnorGate:
		return False

def getControllingInput(gate):
	if type(gate) is AndGate or type(gate) is NandGate: 
		return Zero 
	if type(gate) is OrGate or type(gate) is NorGate: 
		return One
	if type(gate) is XorGate or type(gate) is XnorGate:
		return False

def main():
	filename = "ISCAS85/c499.bench"
	pInputs, pOutputs, wires, gates = parse(filename)
	
	faults = []
	printableInputVecs = []
	
	#inputVec = podem(pInputs[1], One, pInputs, pOutputs, wires, gates)
	#pInputs[1].printSelf()
	#print getPrintableInputVecs(inputVec)
	
	
	
	for mList in wires:
		for index in range(len(mList)): 
			inputVec = podem(mList[index], One, pInputs, pOutputs, wires, gates)
			faults.append(mList[index])
			printableInputVecs.append(getPrintableInputVecs(inputVec))
	
	
	print "++++++++++++++++++++++++++++++++++++++++++++++"
	print "++++++++++++++++++++++++++++++++++++++++++++++"
	print "++++++++++++++++++++++++++++++++++++++++++++++"
	
	for count in range(len(faults)):
		faults[count].printSelf()
		print printableInputVecs[count]

if __name__ == '__main__':
	main()